package easy.MergeTwoSortedLists;

public class MergeTwoSortedLists {
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode(int x) { val = x; }
     * }
     */
    public ListNode mergeTwoLists0(ListNode l1, ListNode l2) {
        ListNode startNode = null;
        ListNode tempNode = new ListNode(0);
        if (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                startNode = l1;
                l1 = l1.next;
            } else {
                startNode = l2;
                l2 = l2.next;
            }
            startNode.next = tempNode;
            while (l1 != null && l2 != null) {
                if (l1.val <= l2.val) {
                    tempNode.val = l1.val;
                    tempNode.next = new ListNode(0);
                    tempNode = tempNode.next;
                    l1 = l1.next;
                } else {
                    tempNode.val = l2.val;
                    tempNode.next = new ListNode(0);
                    tempNode = tempNode.next;
                    l2 = l2.next;
                }
            }
            if (l1 == null) {
                tempNode.val = l2.val;
                tempNode.next = l2.next;
            } else {
                tempNode.val = l1.val;
                tempNode.next = l1.next;
            }
            return startNode;
        } else {
            return l1 != null ? l1 : l2;
        }
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null) return l2;
        if(l2==null) return l1;

        if(l1.val<l2.val){
            ListNode temp = l1;
            temp.next = mergeTwoLists(l1.next,l2);
            return temp;
        }else{
            ListNode temp = l2;
            temp.next = mergeTwoLists(l1,l2.next);
            return temp;
        }
    }
}

